package Hard;

//45.跳跃游戏II
public class Solution45 {
    //2,3,1,2,4,2,3
    //0 1 2 3 4 5 6
    public int jump(int[] nums) {
        //思路：基于贪心策略，看看跳一次最远能跳到哪
        int start = 0;
        int end = nums.length - 1;
        int count = 0;
        while (start < end) {
            int far = 0;
            int far_index = 0;
            //防止数组下标溢出
            int fin = start + nums[start];
            if (fin >= end)
                return ++count;
            for (int i = start + 1; i <= fin; i++) {
                if (i + nums[i] > far) {
                    far = i + nums[i];
                    far_index = i;
                }
            }
            start = far_index;
            count++;
        }
        return count;
    }
}
